package org.czl.leetcode4;

import java.util.Arrays;
import java.util.HashMap;

public class l2963 {
    public static void main(String[] args) {
        System.out.println(numberOfGoodPartitions(new int[]{1, 2, 3, 4}));
    }
    static int MOD = 1_000_000_007;
    public static int numberOfGoodPartitions(int[] nums) {
        int n = nums.length;
        //统计每个数字在数组中出现的最左位置和最右位置
        HashMap<Integer, int[]> map = new HashMap<>();
        int interval = 0;
        for(int i = 0; i < n; i++){
            int ret = nums[i];
            if(!map.containsKey(ret)){
                interval++;
                map.put(ret, new int[]{i,i});
            }
            map.get(ret)[1] = i;
        }
        int[][] set = new int[map.size()][2];
        int index = 0;
        for(Integer i : map.keySet()){
            set[index++] = map.get(i);
        }
        Arrays.sort(set, (a, b) -> a[0] - b[0]);
        int[] ret = null;
        for(int i = 0; i < set.length; i++){
            int L = set[i][0], R = set[i][1];
            if(ret == null || L > ret[1]){
                ret = new int[]{L, R};
            }else{
                ret[1] = Math.max(ret[1], R);
                interval--;
            }
        }
        return (int)pow(2, interval - 1);
    }

    static long pow(long x, long index){
        long ans = 1;
        while(index != 0){
            if( (index & 1) == 1){
                ans = (ans * x) % MOD;
            }
            x = (x * x) % MOD;
            index >>= 1;
        }
        return ans;
    }
}
